import java.util.*;

public class TextDemo {
    static class ListNode{
        int val;
        ListNode next;
        public ListNode(int val){
            this.val = val;
        }
    }
    private ListNode reverse1(ListNode head){
        ListNode prev = null;
        ListNode next = null;
        ListNode cur = head;
        while(cur!=null){
            next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        if(head1==null || head2==null){
            return head1==null ?head2 :head1;
        }
        head1 = reverse(head1);
        head2 = reverse(head2);
        int tem = 0;
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while(head1!=null && head2!=null){
            cur.next = new ListNode((head1.val+head2.val+tem)%10);
            tem = (head1.val+head2.val+tem)/10;
            head1 = head1.next;
            head2 = head2.next;
            cur = cur.next;
        }
        while(head1!=null){
            cur.next = new ListNode((head1.val+tem)%10);
            tem = (head1.val+tem)/10;
            head1 = head1.next;
            cur = cur.next;
        }
        while(head2!=null){
            cur.next = new ListNode((head2.val+tem)%10);
            tem = (head2.val+tem)/10;
            head2 = head2.next;
            cur = cur.next;
        }
        if(tem!=0){
            cur.next = new ListNode(tem);
            cur = cur.next;
        }
        cur = dummy.next;
        dummy.next = null;
        return reverse(cur);

    }
    public static int numSpecial(int[][] mat) {
        int count = 0;
        Map<Integer,Integer> mapi = new HashMap<>();
        Map<Integer,Integer> mapj = new HashMap<>();
        for(int i = 0;i<mat.length;i++){
            for(int j = 0;j<mat[i].length;j++){
                if(mat[i][j]!=0){
                    mapi.put(i,mapi.getOrDefault(i,0)+1);
                    mapj.put(j,mapj.getOrDefault(j,0)+1);
                }
            }
        }
        for(int i = 0;i<mat.length;i++){
            for(int j = 0;j<mat[i].length;j++){
                if((mapi.get(i)!=null && mapi.get(i)==1)&&(mapj.get(j)!=null && mapj.get(j)==1)){
                    count++;
                }
            }
        }
        return count;

    }

    public static void main(String[] args) {
        int[][] array = new int[][]{{1, 0, 0},{0, 0, 1},{1, 0, 0}};
        numSpecial(array);

    }
    public static ListNode detectCycle (ListNode head){
            if (head == null) {
                return null;
            }

        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(slow==fast){
                break;
            }
        }
        if(fast!=null && fast.next!=null){
            return null;
        }
        while(fast!=slow){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    public static void main1(String[] args) {
        ListNode h = new ListNode(1);
        h.next = h;
        detectCycle(h);
    }
    public ListNode mergeKLists(ArrayList<ListNode> lists){
        Queue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val-o2.val;
            }
        });
        for(int i = 0;i<lists.size();i++){
            if(lists.get(i)!=null){
                queue.add(lists.get(i));
            }
        }
        ListNode dummy = new ListNode(-1);
        ListNode head = dummy;
        while(!queue.isEmpty()){
            ListNode tem = queue.poll();
            head.next = tem;
            head = head.next;
            if(tem.next!=null){
                queue.offer(tem.next);
            }
        }
        return dummy.next;
    }
    public ListNode Merge(ListNode list1, ListNode list2) { //两个链表合并
        if(list1 == null) //⼀个已经为空了，直接返回另⼀个
            return list2;
        if(list2 == null)
            return list1;
        ListNode head = new ListNode(0); //加⼀个表头
        ListNode cur = head;
        while(list1 != null && list2 != null){ //两个链表都要不为空
            if(list1.val <= list2.val){ //取较⼩值的结点
                cur.next = list1;
                list1 = list1.next; //只移动取值的指针
            }else{
                cur.next = list2;
                list2 = list2.next; //只移动取值的指针
            }
            cur = cur.next; //指针后移
        }
        if(list1 != null) //哪个链表还有剩，直接连在后⾯
            cur.next = list1;
        else
            cur.next = list2;
        return head.next; //返回值去掉表头
    }
    ListNode divideMerge(ArrayList<ListNode> lists, int left, int
            right){ //划分合并区间
        if(left > right)
            return null;
        else if(left == right) //中间⼀个的情况
            return lists.get(left);
        int mid = (left + right) / 2; //从中间分成两段，再将合并好的两段合并
        return Merge(divideMerge(lists, left, mid), divideMerge(lists,
                mid + 1, right));
    }
    public ListNode mergeKLists1(ArrayList<ListNode> lists) {
        return divideMerge(lists, 0, lists.size() - 1);
    }
    public ListNode Merge1(ListNode list1,ListNode list2) {
        if(list1==null || list2==null){
            return list1==null ?list2: list1;
        }
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while(list1!=null && list2!=null){
            if(list1.val<=list2.val){
                if(dummy.next==null){
                    dummy.next = list1;
                    cur = list1;
                    list1 = list1.next;
                }else{
                    cur.next = list1;
                    cur = list1;
                    list1 = list1.next;
                }
            }else{
                if(dummy.next==null){
                    dummy.next = list2;
                    cur = list2;
                    list2 = list2.next;
                }else{
                    cur.next = list2;
                    cur = list2;
                    list2 = list2.next;
                }
            }
        }
        if(list1==null){
            cur.next = list2;
        }else{
            cur.next = list1;
        }
        return dummy.next;

    }
    public ListNode reverseBetween (ListNode head, int m, int n){
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode cur = head;
        for(int i = 1;i<m;i++){
            prev = cur;
            cur = cur.next;
        }

        for(int i = m;i<n;i++){
            ListNode tem = cur.next;
            cur.next = tem.next;
            tem.next = prev.next;
            prev.next = tem;
        }
        return dummy.next;

    }
    public ListNode reverseBetween1 (ListNode head, int m, int n) {
        // write code here
        if(m==n){
            return head;
        }
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode prev = dummy;
        for(int i = 0;i<m-1;i++){
            prev = prev.next;
        }
        ListNode leftNode = prev.next;

        ListNode rightNode = dummy;
        for(int i = 0;i<n;i++){
            rightNode = rightNode.next;
        }
        ListNode cur = rightNode.next;
        prev.next = null;
        rightNode.next = null;
        reverse(leftNode);

        prev.next = rightNode;
        leftNode.next = cur;
        return dummy.next;
    }
    private void reverse(ListNode head){
        ListNode cur = head;
        ListNode prev = null;
        ListNode next = null;
        while(cur!=null){
            next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
    }
}
